[BAEKJOON] 12100. 2048
Posted on
문제 :
2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.
이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)
자세한 그림 설명은 링크 참조 : https://www.acmicpc.net/problem/12100
이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.
입력 :
첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.
출력 :
최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.
풀이 :
최대 5번만을 이동하고 이동방향도 상, 하, 좌, 우 4방향 뿐이기 때문에 모든 이동을 고려한다 하더라도 4^5 = 1024번의 반복 밖에 일어나지 않기 때문에 브루트포스 방식으로 충분히 접근이 가능하겠다 생각했다.
문제는 2048과 같이 블럭을 이동시키는 것을 어떻게 구현할까에 관해서 조금 생각이 필요했다. 가장 먼저 떠오르는 것은 스택에 쌓아가며 같은 숫자가 나올시 합쳐주는 방식이였기에 그 방식으로 구현을 시작해 보았다.
스택을 사용하면 비교적 간편하게 구현이 가능했지만 두개가 이미 합쳐져서 스택에 쌓인 블럭은 다른 블럭과 다시 합쳐지기 않기 때문에 합친 블럭을 쌓고 난 후에는 반드시 다음 블럭을 아무 조건 없이 스택에 넣어줘야 한다. 이 부분을 놓치기 쉬워 주위가 필요했다.
스택에 쌓은 블럭들은 차례대로 pop하면서 change라는 배열에 이동시킨 블럭들을 셋팅해줬고 다음 이동에서는 change 배열을 board라고 생각하여 이동이 일어나도록 구현했다. ⇒ 재귀방식
코드 :
코드 보기/접기
#include <iostream>
#include <algorithm>
#include <stack>
#include <cstring>
using namespace std;
int n, ans;
void changeBoard(int count, int board[][20]) {
int i, j;
if (count > 5) {
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
ans = max(ans, board[i][j]);
return;
}
stack<int> st;
int change[20][20]{ 0 }, k, cmp, size;
for (j = 0; j < n; j++) {
for (k = n - 1; k > -1; k--) {
cmp = board[j][k];
if (!cmp) continue;
if (st.empty() || st.top() != cmp) st.push(cmp);
else {
st.pop();
st.push(cmp * 2);
while (--k > -1)
if (board[j][k]) {
st.push(board[j][k]);
break;
}
}
}
size = st.size();
for (k = n - size; k < n; k++) {
change[j][k] = st.top();
st.pop();
}
}
changeBoard(count + 1, change);
memset(change, 0, sizeof(change));
for (j = 0; j < n; j++) {
for (k = n - 1; k > -1; k--) {
cmp = board[k][j];
if (!cmp) continue;
if (st.empty() || st.top() != cmp) st.push(cmp);
else {
st.pop();
st.push(cmp * 2);
while (--k > -1)
if (board[k][j]) {
st.push(board[k][j]);
break;
}
}
}
size = st.size();
for (k = n - size; k < n; k++) {
change[k][j] = st.top();
st.pop();
}
}
changeBoard(count + 1, change);
memset(change, 0, sizeof(change));
for (j = 0; j < n; j++) {
for (k = 0; k < n; k++) {
cmp = board[j][k];
if (!cmp) continue;
if (st.empty() || st.top() != cmp) st.push(cmp);
else {
st.pop();
st.push(cmp * 2);
while (++k < n)
if (board[j][k]) {
st.push(board[j][k]);
break;
}
}
}
size = st.size();
for (k = size - 1; k > -1; k--) {
change[j][k] = st.top();
st.pop();
}
}
changeBoard(count + 1, change);
memset(change, 0, sizeof(change));
for (j = 0; j < n; j++) {
for (k = 0; k < n; k++) {
cmp = board[k][j];
if (!cmp) continue;
if (st.empty() || st.top() != cmp) st.push(cmp);
else {
st.pop();
st.push(cmp * 2);
while (++k < n)
if (board[k][j]) {
st.push(board[k][j]);
break;
}
}
}
size = st.size();
for (k = size - 1; k > -1; k--) {
change[k][j] = st.top();
st.pop();
}
}
changeBoard(count + 1, change);
}
int main() {
int i, j, board[20][20];
cin >> n;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
cin >> board[i][j];
changeBoard(1, board);
cout << ans << '\n';
}